package leetcode.hot100;

import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

@SuppressWarnings("all")
public class _139_单词拆分 {

    /**
     * 给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定s 是否可以被空格拆分为一个或多个在字典中出现的单词
     * 说明：
     * 拆分时可以重复使用字典中的单词
     * 你可以假设字典中没有重复的单词
     * 输入: s = "leetcode", wordDict = ["leet", "code"]
     * 输出: true
     * 解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"
     */
    public boolean wordBreak(String s, List<String> wordDict) {
        // 用集合判断元素是否存在更高效
        Set<String> wordDictSet = new HashSet(wordDict);
        // dp[i] 表示字符串 s 前 i 个字符组成的字符串 s[0..i-1] 是否能被空格拆分成若干个字典中出现的单词
        boolean[] dp = new boolean[s.length() + 1];
        // 表示空字符串
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                // 如果s[0,j)单词存在字典中并且s[j,i)也存在字典中，那么就说明s[0,i)字符串是一个可拆分的单词
                if (dp[j] && wordDictSet.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}
